package com.zgkxzx.数据结构.哈希表;

/**
 * 创建者   zgkxzx
 * 创建日期 2018/5/5.
 * 功能描述 开放地址法 线性探测 发生碰撞时候，地址往下加一直到有位置位置
 * - 开放地址法
        - 线性探测 发生碰撞 地址加一 直到有位置
        - 二次探测 增加探测的步长
        - 再哈希 第一个hash发生碰撞后，再调用第二个hash方法hash，两个不能相同
 */
public class HashArrayTable<T> {

    private int size;

    private HashArrayTableEntity hashArrayTableEntitys[];


    public HashArrayTable(int size) {
        this.size = size;
        hashArrayTableEntitys = new HashArrayTableEntity[size];
    }

    /**
     * 得到hash值
     *
     * @param key
     * @return
     */
    private int getHashCode(int key) {
        return (key & 0xfffff) % size;
    }

    /**
     * 插入值
     *
     * @param hashEntity
     */
    public void put(HashArrayTableEntity<T> hashEntity) {
        if (hashEntity == null)
            return;
        //拿到Key
        int key = hashEntity.getKey();
        //hash变换后
        int hashCode = getHashCode(key);

        while (hashArrayTableEntitys[hashCode] != null && hashArrayTableEntitys[hashCode].getKey() != -1) {
            hashCode++;
            hashCode = hashCode % size;
        }

        hashArrayTableEntitys[hashCode] = hashEntity;

    }

    public void put(int key, T value) {
        put(new HashArrayTableEntity<T>(key, value));
    }

    /**
     * 获取摸个值
     *
     * @param key
     * @return
     */
    public HashArrayTableEntity<T> getEntity(int key) {
        //hash变换后
        int hashCode = getHashCode(key);
        while (hashArrayTableEntitys[hashCode].getKey() != key) {
            hashCode++;
            hashCode = hashCode % size;
        }

        return hashArrayTableEntitys[hashCode];
    }

    public T get(int key) {
        return getEntity(key).getValue();
    }


    public void print() {
        for (int i = 0; i < hashArrayTableEntitys.length; i++) {
            System.out.println(i + " --> " + hashArrayTableEntitys[i]);
        }
    }


    /**
     * 定义hash实体
     */
    public static class HashArrayTableEntity<T> {
        private int key = -1;
        private T t;

        public HashArrayTableEntity(int key, T t) {
            this.key = key;
            this.t = t;
        }

        public int getKey() {
            return key;
        }

        public void setKey(int key) {
            this.key = key;
        }

        public T getValue() {
            return t;
        }

        public void setValue(T t) {
            this.t = t;
        }

        @Override
        public String toString() {
            return "HashArrayTableEntity{" +
                    "key=" + key +
                    ", t=" + t +
                    '}';
        }
    }

}
